package com.atwy.tree;

/**
 * 平衡二叉树,Self-balancing binary search tree
 * 解决BST在原本就是有序的序列时退化成链表的问题，
 * <p>
 * 特点：
 * 1.它是一颗空树，或它的左右子树的高度差的绝对值不超过 1；
 * 2.它的左右子树都是一颗平衡二叉树。
 * <p>
 * 高度差平衡且不影响中序遍历结果
 * 实现方法：红黑树、AVL、替罪羊树、Treap、伸展树等。
 * <p>
 * 关键操作，自旋。旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。
 * 所谓的左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。
 * 有以下四种情况：
 * 1.新插入元素位于左子树的左子树，即左左 ，此时右旋达到平衡
 * 2.新插入元素位于右子树的右子树，即右右 ，此时左旋达到平衡
 * <p>
 * 3.新插入元素位于左子树的右子树，即左右 ，此时应先把左子树结点及其右子树进行左旋，成为左左，然后再右旋达到平衡
 * 4.新插入元素位于右子树的左子树，即右左 ，此时应先把右子树结点及其左子树进行右旋，成为右右，然后再左旋达到平衡
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        //int[] ints = {5, 3, 8, 10, 6, 7};
        int[] ints = {10, 11, 7, 6, 8, 9};
        AVLTree tree = new AVLTree();
        tree.add(ints);
        // 利用debug查看树的结构
        tree.middleOrder();
        System.out.println("测试删除结点");
        tree.delNode(8);
        tree.middleOrder();

    }
}

class AVLTree {
    private AVLNode root;

    public void add(int[] ints) {
        if (ints == null) {
            return;
        }
        for (int i = 0; i < ints.length; i++) {
            this.add(new AVLNode(ints[i]));
        }

    }

    public void add(AVLNode node) {
        if (node == null) {
            return;
        }
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
        // 结点添加之后进行平衡
        adjustBalance();
    }

    public void delNode(int value) {
        if (this.root != null) {
            // 1.找到目标结点
            AVLNode targetNode = search(value);
            // 没找到
            if (targetNode == null) {
                return;
            }
            // 如果当前二叉树只有一个结点
            if (this.root.left == null && this.root.right == null) {
                this.root = null;
                return;
            }

            // 1.目标结点只有一个子结点时
            AVLNode parent = searchParent(value);

            if (targetNode.left != null && targetNode.right == null) {// 目标结点只有一个左子结点
                // 目标结点是其父结点的左子结点
                if (parent.left.value == targetNode.value) {
                    parent.left = targetNode.left;
                } else if (parent.right.value == targetNode.value) {
                    parent.right = targetNode.left;
                }
                return;
            }
            if (targetNode.left == null && targetNode.right != null) {// 目标结点只有一个右节点
                // 目标结点是其父结点的左子结点
                if (parent.left.value == targetNode.value) {
                    parent.left = targetNode.right;
                } else if (parent.right.value == targetNode.value) {
                    parent.right = targetNode.right;
                }
                return;
            }
            if (targetNode.left == null && targetNode.right == null) {// 目标结点没有子结点
                if (parent.left.value == targetNode.value) {
                    parent.left = null;
                } else if (parent.right.value == targetNode.value) {
                    parent.right = null;
                }
                return;
            }
            if (targetNode.left != null && targetNode.right != null) {// 目标结点有两个结点
                // 找到目标结点的右子树的最小结点，用临时变量保存
                AVLNode minNode = getMinNode(targetNode.right);
                int temp = minNode.value;
                // 删除右子树的最小节点
                delNode(temp);
                // 目标结点重新赋值
                targetNode.value = temp;
            }
        }
        // 删除某个结点之后进行平衡维护
        adjustBalance();
    }

    /**
     * 得到某结点下右子树最大的子结点
     *
     * @return
     */
    public AVLNode getMaxNode(AVLNode node) {
        if (node == null || node.right == null) {
            return node;
        }
        return node.lastRightNode();
    }

    /**
     * 得到某结点下左子树最小的子结点
     *
     * @return
     */
    public AVLNode getMinNode(AVLNode node) {
        if (node == null || node.right == null) {
            return node;
        }
        return node.lastLeftNode();
    }

    /**
     * 查找目标结点
     *
     * @param value
     * @return
     */
    public AVLNode search(int value) {
        if (this.root == null) {
            return null;
        }
        return this.root.search(value);
    }

    /**
     * 查找目标结点的父结点
     *
     * @param value
     * @return
     */
    public AVLNode searchParent(int value) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchParent(value);
    }

    public void adjustBalance() {
        adjustBalance(root);
    }

    public void adjustBalance(AVLNode node) {
        if (node != null) {
            node.adjustBalance();
        }
    }

    /**
     * 中序遍历
     */
    public void middleOrder() {
        if (this.root == null) {
            System.out.println("树为空，不能遍历~");
            return;
        }
        this.root.middleOrder();
    }
}

class AVLNode {
    int value;
    AVLNode left, right;
    /**
     * 需要平衡调整的最小高度
     */
    public static final int ADJUST_MIN_LEVEL = 3;

    public AVLNode(int value) {
        this.value = value;
    }

    public void add(AVLNode node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {// 比当前结点小，在当前结点的左边
            if (left == null) {
                left = node;
            } else {
                left.add(node);
            }
        } else {
            if (right == null) {
                right = node;
            } else {
                right.add(node);
            }
        }

    }

    public void adjustBalance() {
        // 小于平衡的树需要调整的最小高度，直接返回
        if (height() < ADJUST_MIN_LEVEL) {
            return;
        }
        if (left != null) {
            left.adjustBalance();
        }
        if (right != null) {
            right.adjustBalance();
        }
        int lh = leftHeight() - rightHeight();
        if (Math.abs(lh) <= 1) {
            return;
        }
        // 高度差绝对值大于1，不平衡
        if (lh > 0) {// 左高右低
            int llh = left.leftHeight() - left.rightHeight();
            // 左边高度小于右边，属于左右型
            if (llh <= 1) {
                // 将左子树先左转一次
                leftSpin(left);
            }
            // 然后将当前结点右转
            rightSpin(this);
        } else {// 左低右高
            // 判断右子树的子树高度差，（此时右子树不可能为空）
            int rlh = right.leftHeight() - right.rightHeight();
            // 左边高度大于右边，属于右左型
            if (rlh >= 1) {
                // 将右子树先右转一次
                rightSpin(right);
            }
            // 然后将当前结点左转
            leftSpin(this);
        }
    }

    /**
     * 当前结点的右子结点，是自旋中心轴
     * 左旋相当于绕中心轴逆时针转动
     * 1.新建结点temp替换当前结点，
     * 2.当前结点值变为中心轴结点（演变成中心轴结点，这样就相当于把中心轴提起来了，左就高一层，右就低一层）
     * 3.改变当前结点的右子结点引用，这样中心轴结点就没有引用指向它了，后续会被垃圾回收器回收
     * 4.这样做的好处是，当前结点的父结点对其的引用不需要关心了
     *
     * @param node
     */
    public void leftSpin(AVLNode node) {
        // temp结点替换当前结点
        AVLNode temp = new AVLNode(node.value);
        temp.left = node.left;
        temp.right = node.right.left;
        // 中心轴是 node.right
        // 中心轴的值赋给当前结点，当前结点指向中心轴的引用指向右右子结点
        node.value = node.right.value;
        node.left = temp;
        node.right = node.right.right;
    }

    public void rightSpin(AVLNode node) {
        AVLNode temp = new AVLNode(node.value);
        temp.right = node.right;
        temp.left = node.left.right;

        node.value = node.left.value;
        node.right = temp;
        node.left = node.left.left;
    }

    /**
     * 当前结点是否平衡
     *
     * @return
     */
    private boolean isBalance() {
        int bal = leftHeight() - rightHeight();
        return Math.abs(bal) < 1;
    }

    /**
     * 左子树高度
     *
     * @return
     */
    public int leftHeight() {

        return left == null ? 0 : left.height();
    }

    /**
     * 右子树高度
     *
     * @return
     */
    public int rightHeight() {
        return right == null ? 0 : right.height();
    }

    /**
     * 当前结点高度
     * 空结点高度为0，仅有一个结点高度为 1
     *
     * @return
     */
    public int height() {
        // 左结点为空
        if (left == null) {
            // 左为空，右为空
            if (right == null) {//没有子结点的高度为 1
                return 1;
            }
            // 左为空，右不为
            return right.height() + 1;
        }
        // 左不为空，右为空
        if (right == null) {
            return left.height() + 1;
        }
        // 左右结点都不为空
        int lh = left.height();
        int rh = right.height();
        return lh > rh ? (lh + 1) : (rh + 1);
    }

    /**
     * 根据值查找目标结点
     *
     * @param value
     * @return
     */
    public AVLNode search(int value) {
        if (this.value == value) {
            return this;
        }
        // 比当前值小的查左子树
        if (value < this.value) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        }
        // 比当前值大的查找右子树
        if (this.right == null) {
            return null;
        }
        return this.right.search(value);
    }

    /**
     * 根据值查找目标结点的父结点
     *
     * @param value
     * @return
     */
    public AVLNode searchParent(int value) {
        // 当前结点满足条件，是目标结点的父结点，返回当前结点
        if ((this.left != null && this.left.value == value) ||
                this.right != null && this.right.value == value) {
            return this;
        }
        // 左子树
        if (value < this.value && this.left != null) {
            return this.left.searchParent(value);
        }
        // 右子树
        if (value >= this.value && this.right != null) {
            return this.right.searchParent(value);
        }

        return null;
    }

    /**
     * 得到该结点左子树最左边的叶子结点
     *
     * @return
     */
    public AVLNode lastLeftNode() {
        if (this.left == null) {
            return this;
        }
        return this.left.lastLeftNode();
    }

    /**
     * 得到该结点右子树最右边的叶子结点
     *
     * @return
     */
    public AVLNode lastRightNode() {
        if (this.right == null) {
            return this;
        }
        return this.right.lastRightNode();
    }

    /**
     * 中序遍历
     */
    public void middleOrder() {
        if (left != null) {
            left.middleOrder();
        }
        System.out.println("当前结点：" + value);
        if (right != null) {
            right.middleOrder();
        }
    }
}
